package toOffer;

/**
 * @author YuanAo
 * @date 2024/11/28 16:03
 * @description 查找插入位置
 */

/**
 * 题目：输入一个排序的整数数组nums和一个目标值t，如果数组nums
 * 中包含t，则返回t在数组中的下标；如果数组nums中不包含t，则返回将
 * t 按顺序插入数组nums中的下标。假设数组中没有相同的数字。例如，输
 * 入数组nums为[1, 3, 6, 8]，如果目标值t为3，则输出1；如果 t为5，则返
 * 回2。
 */
public class TO11_2_68 {
    public static void main(String[] args) {
        int[] nums = new int[]{1, 3, 6, 8};
        int target = 8;
        System.out.println(searchInsert(nums, target));
    }

    public static int searchInsert(int[] nums, int target) {
        int left = 0;
        int right = nums.length - 1;
        int mid;
        int result = -1;
        while (left <= right){
            mid = (left + right) >> 1;
            if (nums[mid] == target){
                result = mid;
                break;
            }else if (nums[mid] < target){
                left = mid + 1;
            }else {
                right = mid - 1;
            }
        }
        return result;
    }

}
